import java.util.Stack;

/**
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 *
 * 假设一个二叉搜索树具有如下特征：
 *
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 *
 */
class Solution {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(1);
        TreeNode node5 = new TreeNode(5);
        root.left = node1;
        root.right = node5;
        TreeNode node0 = new TreeNode(0);
        TreeNode node2 = new TreeNode(2);
        node1.left = node0;
        node1.right = node2;
        TreeNode node4 = new TreeNode(4);
        TreeNode node6 = new TreeNode(6);
        node5.left = node4;
        node5.right = node6;

        /*TreeNode root = new TreeNode(3);
        TreeNode node30 = new TreeNode(30);
        root.right = node30;
        TreeNode node10 = new TreeNode(10);
        node30.left = node10;
        TreeNode node15 = new TreeNode(15);
        node10.right = node15;
        TreeNode node45 = new TreeNode(45);
        node15.right = node45;*/
        System.out.println(isValidBST(root));


    }

    /**
     * 我真的是有点蠢，一模一样写都不会写，只能抄过来
     * 这个题目用堆栈来做的确是合理的，遍历整个树，不需要递归（很大的开销）
     *
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        Integer tmp = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (tmp != null && tmp >= curr.val) {
                return false;
            } else {
                tmp = curr.val;
            }
            curr = curr.right;
        }
        return true;
    }


    public boolean isValidBSTByMe(TreeNode root) {
        return helper(root, null, null);
    }

    public boolean helper(TreeNode node, Integer lower, Integer upper) {
        if (node == null) return true;

        int val = node.val;
        // 如果当前值小于应该小于的值或者大于应该大于的值都返回false
        if (lower != null && val <= lower) return false;
        if (upper != null && val >= upper) return false;

        // 递归下去
        if (!helper(node.right, val, upper)) return false;
        return helper(node.left, lower, val);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}